As an increasing number of applications and services are being made available over networks such as the Internet, an increasing number of content, application, and/or service providers are turning to technologies such as cloud computing. Cloud computing, in general, is an approach to providing access to electronic resources through services, such as Web services, where the hardware and/or software used to support those services is dynamically scalable to meet the needs of the services at any given time. A customer typically will rent, lease, or otherwise pay for access to resources through the cloud, such that the customer does not have to purchase and maintain the hardware and/or software to provide access to these resources. In many cases, the resources will include a fleet of host machines or servers that are operable to execute various applications, and in at least some cases can run one or more virtual machines associated with those applications. The environment can be a distributed environment, such that portions of the fleet of servers can be located in different geographical areas. When updates to various applications are to be deployed for a large number of servers in a variety of different areas, it can be desirable to stagger the deployment to these various areas in order to be able to more easily manage and/or monitor aspects of the deployment. For a large number of users who can each deploy a number of application updates to a variety of different servers across the environment, managing the versions and deployments over time can be complex, and failure to properly determine which versions of which applications are deployed on which servers can potentially result in errors or even data loss or corruption, among other such potential problems.